////////////////////////////////////////
// SinglyLinkedList.cpp
//Name: Stephen Durfey && Chris Mares
//Class: CS335
//Prof: Dr. Michael Poor
//Date: 12/4/2008
//Purpose: This program implements the quick sort using a singly linked list. It accepts 2 command line arguments,
//		 as well as 2 flags. The first arugment specifies which file to read into the program.
//		 One flag specifies what type of data structure will be used. The other flag specifies to use a linked list.
//		 Firstly it will sort a list of city data (as specified by the user at the command line) using the quick sort.
//		 While quick sort is running, it will be timed. After the sorting is complete, and the time it ran is determined,
//		 it will print out the first 100 lines of sorted city data, keyed by the last string in the row. After this,
//		 the program will determine the memory footprint of the linked list and report it to the user.

#include "SinglyLinkedList.h"
using namespace std;

////////////////////////////////////////

template <typename T>
SinglyLinkedList<T>::SinglyLinkedList()
: head(0), tail(0)
{
}

template <typename T>
int SinglyLinkedList<T>::size()
{
    int     len = 0;

    for (iterator it = begin(); it != end(); ++it)
        ++len;
    return len;
}

template <typename T>
void SinglyLinkedList<T>::operator=(SinglyLinkedList<T> & y)
{
    head = y.head;
    tail = y.tail;
    y.head = y.tail = 0;
}

////////////////////////////////////////

template <typename T>
typename SinglyLinkedList<T>::iterator
    SinglyLinkedList<T>::iterator::operator++()
{
    ptr = ptr->next;
    return *this;
}

template <typename T>
bool SinglyLinkedList<T>::iterator::operator!=(
    const SinglyLinkedList<T>::iterator & it2) const
{
    return ptr != it2.ptr;
}

template <typename T>
T & SinglyLinkedList<T>::iterator::operator*()
{
    return ptr->value;
}

////////////////////////////////////////

template <typename T>
typename SinglyLinkedList<T>::iterator SinglyLinkedList<T>::begin()
{
    typename SinglyLinkedList<T>::iterator it;

    it.ptr = head;
    return it;
}

template <typename T>
typename SinglyLinkedList<T>::iterator SinglyLinkedList<T>::end()
{
    typename SinglyLinkedList<T>::iterator it;

    it.ptr = 0;
    return it;
}

template <typename T>
void SinglyLinkedList<T>::push_front(const T & x)
{
    Node *p = new Node;

    p->value = x;
    p->next = head;
    head = p;
    if (tail == 0)
    {
 //   	cout << "tail before: " << tail << endl;
    	tail = head;
    	//cout << "tail after: " << tail << endl;
    }
}

/****************************************************************
*  Function: pop_front_push_other_front()
*  Description:
*	This function removes the Node pointed to by the head pointer
*	and pushs that Node onto the front of the list that is passed
*	in as a parameter.
*
****************************************************************/
template <typename T>
void SinglyLinkedList<T>::pop_front_push_other_front(
    SinglyLinkedList<T> & y)
{
    Node* temp = head;
    y.push_front(temp->value);
    head = head->next;
    delete temp;
}

/****************************************************************
*  Function: append_clear_other()
*  Description:
*	This function takes a singly linked list in as a parameter,
*	appends it to the end of the current singly linked list, sets
*	the appropriate private members, and clears the other list.
*
****************************************************************/
template <typename T>
void SinglyLinkedList<T>::append_clear_other(
    SinglyLinkedList<T> & y)
{
	//implicit list is empty AND explicit list isn't
	if(head == 0 && y.head)
	{
		head = y.head;
		tail = y.tail;
	}
	//neither implicit nor explicit list are emptyu
	else if(head && y.head)
	{
		tail->next = y.head;
		tail = y.tail;
	}
	//nothing happens if implicit and explicit lists are empty
	y.tail = y.head = 0;

}


